{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# LRU_cache"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. 问题背景"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们在栈的章节学习了如何实现一个简单的计算器，我们考虑这样一种场景：我们需要实现一个计算器的类，这个类要对于输入的字符串计算式(我们假设合法)返回结果。因为计算器的实现不是本lab的主题，所以我们用python中的eval函数代替。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 定义我们的计算器"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "#定义我们的“计算器”\n",
    "class calculator:\n",
    "    def __init__(self):\n",
    "        pass\n",
    "    def calc(self,s):\n",
    "        assert type(s) == str,'input must be string! Got '+str(type(s))\n",
    "        try:\n",
    "            return eval(s)\n",
    "        except:\n",
    "            print('input error! ',s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 测试一下\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "30\n",
      "129.0\n"
     ]
    }
   ],
   "source": [
    "calc = calculator()\n",
    "print(calc.calc('1+3-2'))\n",
    "print(calc.calc('10*3'))\n",
    "print(calc.calc('123+(3*4)/2'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们的计算器能够正常工作，我们稍微复杂化一下场景，我们把这个计算器做成一个服务，不停地有请求来得到字符串的值。此外，这些请求有可能有很多是一模一样的。对于同样的字符串我们重复计算显然是无意义的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 考虑一个极端例子，我们同一个字符串计算1000次，需要消耗799ms的时间"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 799 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "s = '1+'*1000+'1'\n",
    "for i in range(1000):\n",
    "    calc.calc(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 显然，我们可以将已经有的结果缓存下来，每次字符串来了我们先查询缓存，如果有则返回。\n",
    "### 特别的，字符串比较也是耗时的工作，我们可以将字符串先进行加密，变成hash值。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'d96e018f51ea61e5ff2f9c349c5da67d'"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import hashlib\n",
    "#利用hashlib来得到字符串的md5值\n",
    "def get_hashcode(s):\n",
    "    md5 = hashlib.md5()\n",
    "    md5.update(s.encode())\n",
    "    return md5.hexdigest()\n",
    "#测试一下\n",
    "get_hashcode('1+1')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 然后我们为我们的计算器添加缓存"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "#带缓存的计算器\n",
    "class cache_calculator:\n",
    "    def __init__(self):\n",
    "        #定义缓存\n",
    "        self.cache = {}\n",
    "        pass\n",
    "    def calc(self,s):\n",
    "        assert type(s) == str,'input must be string! Got '+str(type(s))\n",
    "        #计算hash值\n",
    "        hashcode =  get_hashcode(s)\n",
    "        if hashcode in self.cache: return self.cache[hashcode]\n",
    "        \n",
    "        try:\n",
    "            res = eval(s)\n",
    "            #更新hash值\n",
    "            self.cache[hashcode] = res\n",
    "            return res\n",
    "        except:\n",
    "            print('input error! ',s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 我们再来测试一下刚才的例子,可以看到，现在只要8ms了！"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 7.98 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "calc = cache_calculator()\n",
    "s = '1+'*1000+'1'\n",
    "for i in range(1000):\n",
    "    calc.calc(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "再来继续思考问题，如果输入的算式很多呢？特别是在现在的大数据时代，动辄就是上亿的访问。而我们的缓存不可能是无限大小的，因此，一旦我们的缓存满了，就需要有取舍。那么缓存满了怎么办？这就是我们LRU算法需要解决的问题。\n",
    "\n",
    "LRU也是面试中的超高频考题，其本身问题并不复杂，不过要求对各类数据结构都有良好的掌握和理解，也非常贴合实际问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. LRU Cache思想"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "LRU全称是Least Recently Used，即最近最少使用。其核心思想是假如有一个数据很久都没有被访问过了，说明他未来继续被访问的概率也会很低。那么如果我们的缓存满了，这些低概率访问的缓存内容应该优先被清除。\n",
    "\n",
    "而相反，如果某个数据一直频繁被访问，那么这个数据缓存能节省的时间也越大，应当被保留。\n",
    "\n",
    "我们考虑从计算机角度来理解这个事情，我们为每个数据赋予一个优先级，那么如果某个数据一直被访问，他的优先级应当最高，否则如果一直未被访问，他的优先级应该最低，当缓存满了的时候，我们将优先级最低的数据清除出去，将空出来的空间存当前数据。\n",
    "\n",
    "我们学过优先队列，我们假设我们有这么一个优先队列，所有的数都在优先队列里面，每个数都有一个优先级。注意，这里说的\"数\"实际上是`<key,value>`的键值对，随着key和value的不同，LRU也能适应各类场景。\n",
    "\n",
    "我们现在来思考LRU cache的性质：\n",
    "1. 我们说过缓存是有限制的，我们假设容量上限为`capacity`。\n",
    "2. 通过我们的`key`，我们应该能够通过这个cache得到对应的`value`。即我们有方法`get(key)`，返回`value`,如果`key`不存在，我们返回`-1`。\n",
    "3. 如果我们访问了某个`get(key)`，我们应当将这个key的优先级提到最高，因为他刚刚访问过。\n",
    "4. 对应的，我们也需要有`put(key,value)`方法，用于将对应的键值对放进cache中。\n",
    "5. 对于`put`方法，我们put进去的`key`，也需要有目前最高的优先级，因为他也是“刚刚”访问过。\n",
    "6. 如果put时发现cache已经满了，我们需要删除当前优先级最低的键值对。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 堆思想"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们在前面课程中提到过，我们可以用堆来实现优先队列结构。我们先来考虑如何用堆来实现LRU Cache。\n",
    "\n",
    "1. 首先我们有一个堆，堆中存储`<key,priority>`二元组，按`priority`大小来排序。\n",
    "2. 我们另外还有一个`dict`,`dict`中也存储`<key,<value,priority>>`二元组，用于指示`key`对应的二元组是什么。\n",
    "3. 为了方便计算优先级，我们记录全局当前最大的优先级`max_priority`。开始时为0。\n",
    "4. 对于`get(key)`方法：\n",
    "    1. 我们从`dict`中查找`key`对应的二元组。dict查询`O(1)`。\n",
    "    2. 如果没有找到，返回`-1`\n",
    "    3. 我们从堆中删除这个二元组。堆删除`O(log(n))`。\n",
    "    4. 我们修改二元组的`priority`为当前最大值加一，即`max_priority+1`，并将`max_priority`自身加一。`O(1)`。\n",
    "    5. 将新的二元组插入到堆中。堆插入`O(log(n))`。\n",
    "5. 对于`put(key,value)`方法:\n",
    "    1. 先调用`get(key)`，这样如果`key`对应的二元组已存在，就把他放在最靠前的位置。`O(log(n))`。\n",
    "    2. 如果`dict`中已经存在`key`了，直接修改对应的`value`值并返回。`O(1)`。\n",
    "    3. 如果`dict`中不存在`key`，建立二元组`<key,max_priority+1>`，并将`max_priority`自身加一。`O(1)`。\n",
    "    4. 将二元组插入到堆中。`O(log(n))`。\n",
    "    5. 建立二元组`<key,<value,max_priority>>`，将二元组插入到dict中。`O(1)`。\n",
    "    \n",
    "所以我们`put`和`get`方法时间复杂度均为`O(log(n))`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 链表思想"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "显然，我们的数据是根据优先级按顺序出cache的，这很像一个线性的过程，只是在这个线性过程中存在着某些要“插队”数据。所以我们在堆思想中用了堆这种非线性结构来解决这个问题。\n",
    "\n",
    "我们思考一下是否能用线性结构来解决这个问题。假如说我们按照优先级把所有的数据排成一列，最前面的数据优先级最高，最后面的数据优先级最低。\n",
    "先来思考一下我们的操作：\n",
    "1. get：我们需要把某一个数据拿出来放在开头，其余数据保持顺序。\n",
    "2. put：我们需要把一个新数据放在开头，如果长度超限我们需要移除末尾元素。\n",
    "\n",
    "那么显然对于get，我们把某一个数据从列中拿出来并且放在开头的操作，**链表**是非常合适的。从链表中插入和删除节点复杂度均为O(1)。\n",
    "\n",
    "那么我们考虑用链表来维护这个cache数据结构，来细化一下所需要的操作：\n",
    "1. 对于`get(key)`:\n",
    "    1. 我们需要知道`key`在链表中是否存在以及具体位置。链表本身不支持随机查询，不过我们同样可以用dict来存储`key`对应的节点。\n",
    "    2. 我们需要从链表中删除一个中间节点，并且保持链表顺序，所以这个中间节点需要同时知道其前驱和后继，这也说明了这个链表需要是一个**双向链表**。\n",
    "    3. 我们还需要将节点插入到链表头部，所以我们需要知道头部的位置，也即记录头指针`head`。\n",
    "2. 对于`put(key,value)`:\n",
    "    1. 我们可以用类似之前的方法来判断链表中是否存在目标节点，如果存在则将其提前。\n",
    "    2. 如果cache满了，我们需要删除最后一个节点，所以我们需要记录尾指针`tail`。\n",
    "    3. 同样，如果cache没满。我们也需要在尾部插入节点。\n",
    "    \n",
    "\n",
    "接下来我们考虑动手实现一个LRU Cache\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. LRU Cache的实现"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 定义链表节点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "#首先我们定义链表节点，我们的链表是一个双链表，所以有pre和next两个指针，同时，我们还需要存节点的key和value值\n",
    "class node:\n",
    "    def __init__(self,value=0,key=0):\n",
    "        #前一个指针\n",
    "        self.pre = None\n",
    "        #后一个指针\n",
    "        self.next = None\n",
    "        #value值\n",
    "        self.value = value\n",
    "        #key值\n",
    "        self.key = key"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 定义LRU类"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "#我们接下来定义我们的LRU类，我们先看看需要哪些方法\n",
    "\n",
    "class LRUCache(object):\n",
    "    #初始化方法，capacity是Cache的容量\n",
    "    def __init__(self, capacity):\n",
    "        pass\n",
    "\n",
    "    #我们需要能够在开头插入节点\n",
    "    def insert_at_head(self,node):\n",
    "        pass\n",
    "    \n",
    "    #我们同样也需要能够删除最后一个节点\n",
    "    def erase_at_tail(self):\n",
    "        pass\n",
    "    \n",
    "    #核心的get方法\n",
    "    def get(self, key):\n",
    "        pass\n",
    "\n",
    "    #核心的put方法\n",
    "    def put(self, key, value):\n",
    "        pass\n",
    "            \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 初始化方法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "    #先来看我们的初始化部分，我们前面提到过，我们需要一个dict来存储key和node的对应关系，需要head和tail指针\n",
    "    def __init__(self, capacity):\n",
    "        #存储key和node对应关系的dict\n",
    "        self.mp = {}\n",
    "        #头尾指针\n",
    "        self.tail = None\n",
    "        self.head = None\n",
    "        #我们同样定义最大的缓存容量，以及已用的存储容量\n",
    "        self.capacity = capacity\n",
    "        self.count = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 在开头插入一个节点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "    def insert_at_head(self,node):\n",
    "        if self.count == 0:\n",
    "            #先考虑边界条件，如果count=0，当前节点就是唯一节点，当然是头结点和尾节点了\n",
    "            self.head = node\n",
    "            self.tail = node\n",
    "        else:\n",
    "            #否则我们先找到头结点，把当前节点链在头结点前面\n",
    "            node.next = self.head\n",
    "            self.head.pre = node\n",
    "            #注意我们需要更新现在的头结点\n",
    "            self.head = node\n",
    "        #插入节点了count当然加一，并且把key和node放在我们的dict中\n",
    "        self.count += 1\n",
    "        self.mp[node.key] = node"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 在尾部删除一个节点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "    def erase_at_tail(self):\n",
    "        #如果当前没有节点当然也不存在删除最后一个节点的事情了\n",
    "        if self.count == 0: return \n",
    "        \n",
    "        #取出当前尾部节点\n",
    "        n_node = self.tail\n",
    "        if self.count == 1:\n",
    "            #如果当前只有一个节点，那么删除完就全空了\n",
    "            self.head = None\n",
    "            self.tail = None\n",
    "        else:\n",
    "            #否则我们把tail节点指向当前节点的前一个节点，并断开连接\n",
    "            self.tail = n_node.pre\n",
    "            self.tail.next = None\n",
    "            \n",
    "        #最后我们从map中删除当前节点\n",
    "        n_node.pre = None\n",
    "        n_node.next = None\n",
    "        n_key = n_node.key\n",
    "        self.mp.pop(n_key)\n",
    "        \n",
    "        #当然count也要减一\n",
    "        self.count -= 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### get方法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "    def get(self, key):\n",
    "        #首先考虑边界，如果key不在dict中，我们直接返回-1\n",
    "        if not key in self.mp: return -1\n",
    "        \n",
    "        #取出key所对应的节点\n",
    "        n_node = self.mp[key]\n",
    "        \n",
    "        #第一种情况，如果这个节点就是头结点了，也不存在将其挪到开头的事情了，我们直接返回value\n",
    "        if n_node == self.head: return n_node.value\n",
    "        \n",
    "        #对于其他情况，我们需要将其从链表中删除，并挪到开头，我们先考虑删除。\n",
    "        \n",
    "        #我们先取出其前一个和后一个节点\n",
    "        pre_node = n_node.pre\n",
    "        next_node = n_node.next\n",
    "        \n",
    "        if n_node == self.tail:\n",
    "            #如果这个节点是尾部节点，直接调用方法删除尾部节点。\n",
    "            self.erase_at_tail()\n",
    "        else:\n",
    "            #否则我们删除这个节点\n",
    "            \n",
    "            #1.先将其前后节点连起来\n",
    "            pre_node.next = next_node\n",
    "            next_node.pre = pre_node\n",
    "            \n",
    "            #2.删除这个节点\n",
    "            n_node.pre = None\n",
    "            n_node.next = None\n",
    "            n_key = n_node.key\n",
    "            self.mp.pop(n_key)\n",
    "            self.count -= 1\n",
    "        \n",
    "        #最后，我们将这个节点插入到开头\n",
    "        self.insert_at_head(n_node)\n",
    "        \n",
    "        return n_node.value\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### put方法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "    def put(self, key, value):\n",
    "        #首先我们调用get方法，如果未返回-1，说明其已经在map中有了。\n",
    "        #由于我们调用get以后会把这个节点挪到开头，所以这种情况下我们直接修改头结点的值就可以了。\n",
    "        if self.get(key) != -1:\n",
    "            self.head.value = value\n",
    "            return\n",
    "        #如果容量满了，我们先删除最后一个节点\n",
    "        if self.count == self.capacity:\n",
    "            self.erase_at_tail()\n",
    "        \n",
    "        #最后我们定义一个新节点，把新节点插入到开头\n",
    "        n_node = node(value,key)\n",
    "        self.insert_at_head(n_node)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 代码全貌，你可以尝试不依赖注释看懂每一个部分的内容。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LRUCache(object):\n",
    "    def __init__(self, capacity):\n",
    "        self.mp = {}\n",
    "        self.tail = None\n",
    "        self.head = None\n",
    "        self.capacity = capacity\n",
    "        self.count = 0\n",
    "\n",
    "    def insert_at_head(self,node):\n",
    "        if self.count == 0:\n",
    "            self.head = node\n",
    "            self.tail = node\n",
    "        else:\n",
    "            node.next = self.head\n",
    "            self.head.pre = node\n",
    "            self.head = node\n",
    "        self.count += 1\n",
    "        self.mp[node.key] = node\n",
    "    \n",
    "    def erase_at_tail(self):\n",
    "        if self.count == 0: return \n",
    "        n_node = self.tail\n",
    "        if self.count == 1:\n",
    "            self.head = None\n",
    "            self.tail = None\n",
    "        else:\n",
    "            self.tail = n_node.pre\n",
    "            self.tail.next = None\n",
    "            \n",
    "        n_node.pre = None\n",
    "        n_node.next = None\n",
    "        n_key = n_node.key\n",
    "        self.mp.pop(n_key)\n",
    "        \n",
    "        self.count -= 1\n",
    "            \n",
    "    def get(self, key):\n",
    "        if not key in self.mp: return -1\n",
    "        \n",
    "        n_node = self.mp[key]\n",
    "        if n_node == self.head: return n_node.value\n",
    "        \n",
    "        pre_node = n_node.pre\n",
    "        next_node = n_node.next\n",
    "        \n",
    "        if n_node == self.tail:\n",
    "            self.erase_at_tail()\n",
    "        else:\n",
    "            pre_node.next = next_node\n",
    "            next_node.pre = pre_node\n",
    "            n_node.pre = None\n",
    "            n_node.next = None\n",
    "            n_key = n_node.key\n",
    "            self.mp.pop(n_key)\n",
    "            self.count -= 1\n",
    "        \n",
    "        \n",
    "        self.insert_at_head(n_node)\n",
    "        \n",
    "        return n_node.value\n",
    "\n",
    "    def put(self, key, value):\n",
    "        if self.get(key) != -1:\n",
    "            self.head.value = value\n",
    "            return\n",
    "        \n",
    "        if self.count == self.capacity:\n",
    "            self.erase_at_tail()\n",
    "        \n",
    "        \n",
    "        n_node = node(value,key)\n",
    "        self.insert_at_head(n_node)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 4. 使用LRU Cache"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "我们现在考虑把LRU用在我们的计算器中。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "#先定义最大缓存\n",
    "max_cache_size = 10\n",
    "\n",
    "#LRU缓存的计算器\n",
    "class LRU_calculator:\n",
    "    def __init__(self):\n",
    "        #定义缓存\n",
    "        self.cache = LRUCache(max_cache_size)\n",
    "        pass\n",
    "    def calc(self,s):\n",
    "        assert type(s) == str,'input must be string! Got '+str(type(s))\n",
    "        #计算hash值\n",
    "        hashcode =  get_hashcode(s)\n",
    "        \n",
    "        #尝试从LRU Cache中取值\n",
    "        res = self.cache.get(hashcode)\n",
    "        if res != -1: return res\n",
    "        \n",
    "        try:\n",
    "            res = eval(s)\n",
    "            #更新LRU\n",
    "            self.cache.put(hashcode,res)\n",
    "            return res\n",
    "        except:\n",
    "            print('input error! ',s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可以看到，修改非常的简单。且同样只需要9ms，当然这只是一个重复的例子，并没有完全发挥LRU的作用，你可以尝试用更多的例子来进行测试。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 8.98 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "calc = LRU_calculator()\n",
    "s = '1+'*1000+'1'\n",
    "for i in range(1000):\n",
    "    calc.calc(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5.总结"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们介绍了LRU Cache的实现思路，LRU Cache很好地缓解了了当缓存容量有限时的效率问题，其实现也非常明了和简洁。实际上在工业界，LRU也是非常常用的策略，这也是其作为高频面试题的原因之一。掌握LRU也能很好地帮助我们理解计算机的缓存机制，优化我们的代码效率。\n",
    "\n",
    "和其他部分一样,我们同样留一些小思考：\n",
    "1. LRU Cache各个操作的时间复杂度是多少？\n",
    "2. 如果我们不同的key数量非常有限，我们还需要使用LRU么？应该如何优化算法？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3(py37)",
   "language": "python",
   "name": "py37"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
